/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DickYang
 * Date: 2023-06-30
 * Time: 16:43
 */
public class MySingleList {

    private Node head;

/*    public void createList() {
        Node node1 = new Node(10);
        Node node2 = new Node(340);
        Node node3 = new Node(56);
        Node node4 = new Node(134);
        Node node5 = new Node(99);

        head = node1;
        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
    }*/

    public Node getHead() {
        return head;
    }

    public void setHead(Node head) {
        this.head = head;
    }

    public void display(){
        Node cur = head;
        while(cur != null) {
            System.out.print(cur.getVale() + " ");
            cur = cur.getNext();
        }
        System.out.println();
    }
    public void display(Node newHead){
        Node cur = newHead;
        while(cur != null) {
            System.out.print(cur.getVale() + " ");
            cur = cur.getNext();
        }
        System.out.println();
    }
    //得到单链表的长度
    public int size(){
        Node cur = head;
        int count = 0;
        while(cur != null) {
            cur = cur.getNext();
            count++;
        }
        return count;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        Node cur = head;
        while(cur != null) {
            if (cur.getVale() == key) {
                return true;
            }
            cur = cur.getNext();
        }
        return false;
    }
    //头插法
    public void addFirst(int data){
        Node node = new Node(data);
        node.setNext(head);
        head = node;
    }
    //尾插法
    public void addLast(int data){
        Node node = new Node(data);
        Node cur = head;
        //没有节点时,默认头插
        if (cur == null) {
            addFirst(data);
            return;
        }
        //找到尾巴节点
        while(cur.getNext() != null) {
            cur = cur.getNext();
        }
        cur.setNext(node);
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index > size()) {
            throw new IndexOutOfException("下标访问错误!!,请检查下标");
        }

        Node node = new Node(data);
        Node cur = prevIndex(index);
        node.setNext(cur.getNext());
        cur.setNext(node);
    }
    //找到Index位置前一个节点地址
    private Node prevIndex(int index) {
        Node cur = head;
        int count = 1;
        while(count < index) {
            cur = cur.getNext();
            count++;
        }
        return cur;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        Node cur = head;
        //删除第一个节点
        if (head.getVale() == key) {
            head = head.getNext();
        } else {
            //找到key前一个节点
            cur = prevKey(key);
            cur.setNext(cur.getNext().getNext());
        }
    }
    private Node prevKey(int key) {
        Node cur = head;

        while(cur.getNext().getVale() != key) {
            cur = cur.getNext();
        }
        return cur;
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if (head == null) {
            return;
        }
        Node cur = head.getNext();
        Node prev = head;

        while(cur != null) {
            if (cur.getVale() == key) {
                prev.setNext(cur.getNext());
                cur = cur.getNext();
            } else {
                prev = cur;
                cur = cur.getNext();
            }
        }
        //key在开头节点
        if (head.getVale() == key) {
            head = head.getNext();
        }
    }
    public void clear(){
        head = null;
    }




    //翻转链表
    public Node reverseList() {
        if (head == null) {
            return null;
        }
        if (head.getNext() == null) {
            return head;
        }

        Node cur = head.getNext();
        Node curNext = cur.getNext();
        head.setNext(null);
        //头插法
        while(cur != null && cur.getNext() != null) {
            cur.setNext(head);
            head = cur;
            cur = curNext;
            curNext = cur.getNext();
        }

        cur.setNext(head);
        head = cur;

        return head;
    }
    //返回链表的中间节点
    public Node middleNode() {
        if (head == null) {
            return null;
        }
        Node fast = head; // 快指针
        Node show  = head; // 慢指针
        while(fast != null && fast.getNext() != null) {
            fast = fast.getNext().getNext();
            show = show.getNext();
        }
        return show;
    }

    //链表中倒数第K个节点
    public Node FindKthToTail(int k) {
        //判断K的有效性 ,如果k的值小于或等于0
        if (k <= 0 || head == null) {
            return null;
        }

        Node fast = head;
        Node show = head;

        while(k-1 != 0) {
            //判断K的有效性,如果K的值给大了
            if (fast.getNext() == null) {
                return null;
            }

            fast = fast.getNext();
            k--;
        }
        while(fast.getNext() != null) {
            fast = fast.getNext();
            show = show.getNext();
        }
        return show;
    }

    //合并两个有序链表
    public Node mergeTwoLists(Node list1, Node list2) {

        Node newNode = new Node(0);
        Node tmp = newNode;

        while (list1 != null && list2 != null) {
            if (list1.getVale() <= list2.getVale()) {
                tmp.setNext(list1);
                tmp = tmp.getNext();
                list1 = list1.getNext();
            }else {
                tmp.setNext(list2);
                tmp = tmp.getNext();
                list2 = list2.getNext();
            }
        }
        if (list2 == null) {
            tmp.setNext(list1);
        }
        if (list1 == null) {
            tmp.setNext(list2);
        }
        return newNode.getNext();
    }

    //判断链表是否为回文结构
    public boolean chkPalindrome(Node head) {
        Node fast = head;
        Node show = head;

        //找到中间节点
        while(fast != null && fast.getNext() != null) {
            fast = fast.getNext().getNext();
            show = show.getNext();
        }

        Node cur = show.getNext();

        //翻转
        while(cur != null) {
            Node curNext = cur.getNext();
            cur.setNext(show);
            show = cur;
            cur = curNext;
        }

        //判断
        while(head != show){
            if (head.getVale() == show.getVale()) {
                if (head.getNext() == show) {
                    return true;
                }
                head = head.getNext();
                show = show.getNext();
            }else {
                return false;
            }
        }
        return true;
    }

    //链表分割,给一个x 比x小的节点放在x之前,不能改变原来的顺序
    public Node partition(Node Head, int x) {
        // write code here
        Node cur = head;
        Node ds = null;
        Node de = null;
        Node xs = null;
        Node xe = null;

        while(cur != null) {
            if (cur.getVale() <= x) {
                if (xs != null) { // 判断是否为第一次插入
                    xe.setNext(cur);
                    xe = cur;
                } else {
                    xs = cur;
                    xe = cur;
                }
            } else {
                if (ds != null) { // 判断是否为第一次插入
                    de.setNext(cur);
                    de = cur;
                } else {
                    ds = cur;
                    de = cur;
                }
            }
            cur = cur.getNext();
        }
//        if (xs == null) { // 全部小于x
//            return ds;
//        }
        if (xs == null) { // 全部大于x
            return ds;
        }
        // 链接  -  既有小于x又有大于x的
        xe.setNext(ds);
        if (de != null ) {
            de.setNext(null);
        }
        return xs;
    }

    //相交链表
    public Node getIntersectionNode(Node headA, Node headB) {
        //判断如果其中有一个链表为空,则没有交点,返回空
        if (headA == null || headB == null) {
            return null;
        }
        //定义两个临时变量引用这两个链表
        Node curL = headA;
        Node curS = headB;

        //计算两个链表相交节点之前的元素个数,并求出个数差
        int lenL = size(headA);
        int lenS = size(headB);
        int len = lenL - lenS;

        //保证lenL里面的个数永远比lenS多
        if (len < 0) {
            curL = headB;
            curS = headA;
            len = lenS - lenL;
        }
        //先让元素多的先走差值步
        while(len != 0){
            curL = curL.getNext();
            len--;
        }
        //同时走
        while(curL != curS) {
            curL = curL.getNext();
            curS = curS.getNext();
        }
        return curL;  //不相交
    }
    private int size(Node head) {
        Node cur = head;
        int count = 0;
        if (cur != null) {
            count++;
        }
        return count;
    }

    //判断链表是否有环
    public boolean hasCycle(Node head) {
        Node fast = head;//快指针
        Node show  = head; //慢指针

        while(fast != null && fast.getNext() != null) {
            fast = fast.getNext().getNext();
            show = show.getNext();

            if (fast == show) {
                return true;
            }
        }
        return false;
    }

    //返回环形链表开始入环的第一个节点
    public Node detectCycle(Node head) {
        Node fast = head;//快指针
        Node show  = head; //慢指针

        while(fast != null && fast.getNext() != null) {
            fast = fast.getNext().getNext();
            show = show.getNext();

            if (fast == show) {
                break;
            }
        }
        if (fast == null || fast.getNext() == null) {
            return null;
        }
        show = head;
        while(show != fast) {
            show = show.getNext();
            fast = fast.getNext();
        }
        return fast;
    }
}
